package com.itheima.datastructure.priorityqueue;

import com.itheima.datastructure.queue.Queue;

public class PriorityQueue4 <E extends Priority> implements Queue<E> {
    Priority[] array;
    int size;

    public PriorityQueue4(int capacity) {
        array=new Priority[capacity];
    }

    @Override
    public boolean offer(E offered) {
        if(isFull()){
            return false;
        }
        //末尾要添加的元素
        int child=size++;
        //父节点位置
        int parent=(child-1)/2;
        //如果大于父节点
        while(child>0 && offered.priority()>array[parent].priority()){
            //父节点下移
            array[child]=array[parent];
            child=parent;
            parent=(child-1)/2;
        }
        array[child]=offered;
        return true;
    }


    @Override
    public E poll() {
      if(isEmpty()){
          return null;
      }
      //将最小与堆顶进行交换
      swap(0,size-1);
      size--;
      //最大的元素
      Priority e=array[size];
      array[size]=null;
      down(0);
      return (E)e;
    }

    private void down(int parent){
        int left=2*parent+1;
        int right=left+1;
        int max=parent;//假设父元素优先级最高
        if(left<size && array[left].priority()>array[max].priority()){
            max=left;
        }
        if(right<size && array[right].priority()>array[max].priority()){
            max=right;
        }
        if(max!=parent){
            swap(max,parent);
            down(max);
        }
    }
    private void swap(int i,int j){
        Priority t=array[i];
        array[i]=array[j];
        array[j]=t;
    }


    @Override
    public E peek() {
         if(isEmpty()){
             return null;
         }
         return (E)array[0];
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean isFull() {
        return size== array.length;
    }
}
